/**
 * @ClassName KP22_bitMap2
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/16 15:39
 */

import java.util.HashSet;

/**
 * 从0开始存储
 * 位图 用 & >> 来实现位图数字的存储，效率较慢
 * 暂且考虑存储的数字为正数
 *
 * 所有的 num - 0 >> 6 ---> num - start >> 6
 * 所有的 1L << ((num - start) & 63)
 * 就变成了任意数字区间的值
 */
public class KP22_bitMap2 {
    public static class BitMap {
        public long[] bits;

        /**
         * 存储范围：0~max
         *
         * @param max
         */
        public BitMap(int max) {
            // 根据最大值生成数组的个数（多少个数组空间能包含0-max的数）
            bits = new long[(max + 64) >> 6];
        }

        public void offer(int num) {
            // num - 0 / 64 表示数num存放的数组空间位置
            // num - 0 & 63 表示num在这个空间的位置信息
            bits[num >> 6] |= (1L << (num & 63));
        }

        public void remove(int num) {
            bits[num >> 6] &= ~(1L << (num & 63));
        }

        public boolean isContains(int num) {
            return (bits[num >> 6] & (1L << (num & 63))) != 0;
        }
    }

    public static void testBitMap() {
        double start = System.currentTimeMillis();
        System.out.println("测试开始！");
        int max = 10000;
        int testTimes = 100000000;
        KP22_bitMap1.BitMap bitMap = new KP22_bitMap1.BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < testTimes; i++) {
            int num = (int) (Math.random() * (max + 1));
            double decide = Math.random();
            if (decide < 0.33) {
                bitMap.offer(num);
                set.add(num);
            } else if (decide < 0.66) {
                bitMap.remove(num);
                set.remove(num);
            } else {
                if (bitMap.isContains(num) != set.contains(num)) {
                    System.out.println("error1 num:" + num);
                    break;
                }
            }
        }
        for (int i = 0; i < max; i++) {
            if (bitMap.isContains(i) != set.contains(i)) {
                System.out.println("error" + i);
            }
        }
        double end = System.currentTimeMillis();
        System.out.println("测试结束！");
        System.out.println("消耗时间：" + (end - start));
    }

    public static void main(String[] args) {
        testBitMap();
    }
}
